/**************************************************************************
* File:            main.cpp                                               *
* Description:     Main testing unit for graph.h, search.h, topsort.h     *
* Author:          Zhuk Artsem, 399                                       *
**************************************************************************/

#define _CRTDBG_MAP_ALLOC
#include <stdlib.h>
#include <crtdbg.h>

#include <iostream>
#include <vector>
#include <algorithm>
#include "graph.h"
#include "search.h"
#include "topsort.h"
#include "searchtester.h"
#include "graphgen.h"
#include "gtest\gtest.h"
#include <stdlib.h>
#include <iostream>
#include <crtdbg.h>
#include <functional>

bool hasCycle(Graph const * graph){
	int n = graph->getVerticesNumber();
	std::vector<std::vector<bool>> reachable(n, std::vector<bool>(n));

	for (int i = 0; i < n; ++i){
		std::vector<int> incidenceList = graph->getIncidenceList(i);
		for (auto &to : incidenceList)
			reachable[i][to] = true;
	}

	for (int k = 0; k < n; ++k)
	for (int i = 0; i < n; ++i)
	for (int j = 0; j < n; ++j)
	if (reachable[i][k] && reachable[k][j])
		reachable[i][j] = true;

	for (int i = 0; i < n; ++i)
	for (int j = i + 1; j < n; ++j)
	if (reachable[i][j] && reachable[j][i])
		return true;

	return false;
}

template<typename T>
bool isEqual(std::vector<T> x, std::vector<T> y){
	std::sort(x.begin(), x.end());
	std::sort(y.begin(), y.end());
	return x == y;
}

bool isValidTopSort(std::vector<int> order, Graph const * graph){
	if (hasCycle(graph))
		return order.empty();

	int n = graph->getVerticesNumber();

	if (order.size() != n)
		return false;

	std::vector<int> index(n);

	for (int i = 0; i < n; ++i)
		index[order.at(i)] = i;

	for (int i = 0; i < n; ++i){
		for (int &to : graph->getIncidenceList(i))
		if (index[i]>index[to])
			return false;
	}
	return true;
}

TEST(Graph, construtor){
	for (int i = 0; i < 10; i++)
	{

		int n = 300;
		std::vector<Edge> edges = getRandomEdges(n, 0.01*(rand()%100));

		ListBasedGraph ListBasedGraph(edges, n);
		MatrixGraph matrixGraph(edges, n);

		std::vector<Edge> ListBasedGraphEdges;
		std::vector<Edge> matrixGraphEdges;

		for (int i = 0; i < n; ++i){
			std::vector<int> ListBasedGraphList = ListBasedGraph.getIncidenceList(i);
			std::vector<int> matrixGraphList = matrixGraph.getIncidenceList(i);
			for (int to : ListBasedGraphList)
				ListBasedGraphEdges.emplace_back(i, to);
			
			for (int to : matrixGraphList)
				matrixGraphEdges.emplace_back(i, to);
			
		}

		EXPECT_TRUE(isEqual<Edge>(edges, ListBasedGraphEdges));
		EXPECT_TRUE(isEqual<Edge>(edges, matrixGraphEdges));	
	}
}

TEST(Graph, getVericesNumber){
	for (int i = 1; i <= 10; ++i){
		std::vector<Edge> edges = getRandomEdges(i, 0.5);
		ListBasedGraph ListBasedGraph(edges, i);
		MatrixGraph matrixGraph(edges, i);
		EXPECT_EQ(i, ListBasedGraph.getVerticesNumber());
		EXPECT_EQ(i, matrixGraph.getVerticesNumber());
	}
}

TEST(Graph, getIncidenceList){
	for (int i = 1; i <= 100; ++i){
		int n = 20;
		std::vector<Edge> edges = getRandomEdges(n, 0.5);
		ListBasedGraph listBasedGraph(edges, n);
		MatrixGraph matrixGraph(edges, n);

		for (int vertex = 0; vertex < n; ++vertex){
			std::vector<int> list, matrixBaseGraphList = matrixGraph.getIncidenceList(vertex), listBasedGraphList = listBasedGraph.getIncidenceList(vertex);
			for (Edge &edge : edges)
			if (edge.from == vertex){
				list.push_back(edge.to);
			}

			EXPECT_TRUE(isEqual(list, matrixBaseGraphList));
			EXPECT_TRUE(isEqual(list, listBasedGraphList));
		}
	}
}

TEST(Graph, makeCompactGraph){
	/* graphs with small density (0.1)*/
	/* assumed to be stored as a list */
	for (int i = 10; i < 100; ++i){
		EXPECT_TRUE(NULL != dynamic_cast<ListBasedGraph *>(getRandomGraph(i, 0.1).get()));
	}

	/* graphs with big density (0.9) */
	/* assumed to be stored as a matrix */
	for (int i = 10; i < 100; ++i){
		EXPECT_TRUE(NULL != dynamic_cast<MatrixGraph *>(getRandomGraph(i, 0.9).get()));
	}

} 

TEST(Topsort, correctness){
	/* test on all graphs of size <=5 */

	for (int i = 1; i <= 5; ++i)
	for (auto &graph : getAllGraphs(i))
		EXPECT_TRUE(isValidTopSort(topSort(graph.get()), graph.get()));

	/* test on big graphs with differen density */

	for (int i = 0; i < 100; ++i){
		int vertexNumber = 300;
		double density = 0.01*i;
		std::unique_ptr<Graph> graph = makeCompactGraph(getRandomEdges(vertexNumber, density), vertexNumber);
		EXPECT_TRUE(isValidTopSort(topSort(graph.get()), graph.get()));
	}

}

TEST(Topsort, speed){
	clock_t start, finish;
	
	{
		int n = 1000;
		std::unique_ptr<Graph> graph = getFullGraph(n);
		start = clock();
		topSort(graph.get());
		finish = clock();
		std::cout << "On full graph: " << (finish - start) << "\n";
	}

	{
		int n = 1000;
		std::unique_ptr<Graph> graph = getFunctionalGraph(n, [](int x){return x*x; });
		start = clock();
		topSort(graph.get());
		finish = clock();
		std::cout << "On functional (x*x) graph: " << (finish - start) << "\n";
	}

	{
		int n = 1000;
		std::unique_ptr<Graph> graph = getFunctionalGraph(n, [](int x){return x / 2; });
		start = clock();
		topSort(graph.get());
		finish = clock();
		std::cout << "On functional (x/2) graph: " << (finish - start) << "\n";
	}

}

TEST(DFS, general){
	TestingVisitor visitor;

	/* on small graphs */
	for (int i = 1; i <= 5; ++i){
		visitor.setGraphSize(i);
		for (auto &graph : getAllGraphs(i)){
			runDFS(graph.get(), &visitor);

			EXPECT_TRUE(visitor.isGood());

			visitor.reset();
		}
	}


	/* on big graphs */
	int n = 100;
	visitor.setGraphSize(n);
	for (int i = 0; i <= 100; ++i){
		runDFS(getRandomGraph(n, 0.01*i).get(), &visitor);
		EXPECT_TRUE(visitor.isGood());
		visitor.reset();
	}

}

TEST(BFS, general){
	TestingVisitor visitor;

	/* on small graphs */
	for (int i = 1; i <= 5; ++i){
		visitor.setGraphSize(i);
		for (auto &graph : getAllGraphs(i)){
			BFS(0, graph.get(), &visitor);
			EXPECT_TRUE(visitor.everyVertexClosed());
			visitor.reset();
		}
	}


	/* on big graphs */
	int n = 100;
	visitor.setGraphSize(n);
	for (int i = 0; i <= 100; ++i){
		BFS(0, getRandomGraph(n, 0.01*i).get(), &visitor);
		EXPECT_TRUE(visitor.everyVertexClosed());
		visitor.reset();
	}


}

TEST(Edge, operators){
	int n = 100;
	std::vector<std::pair<int, int>> pairs;
	std::vector<Edge> edges;
	for (int i = 0; i < n; ++i){
		int x = rand();
		int y = rand();
		pairs.emplace_back(x, y);
		edges.emplace_back(x, y);
	}

	for (int i = 0; i < n; ++i)
	for (int j = 0; j < n; ++j){
		EXPECT_EQ(pairs[i] < pairs[j], edges[i] < edges[j]);
		EXPECT_EQ(pairs[i] == pairs[j], edges[i] == edges[j]);
		EXPECT_EQ(pairs[i] != pairs[j], edges[i] != edges[j]);
	}
}

int main(int argc, char ** argv){

	::testing::InitGoogleTest(&argc, argv);
	srand(347);

	
	return RUN_ALL_TESTS();
}